package leetCode.solution;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Random;

/**
 * Given an integer array nums and an integer k, return the kth largest element
 * in the array.
 * 
 * Note that it is the kth largest element in the sorted order, not the kth
 * distinct element.
 * 
 * You must solve it in O(n) time complexity.
 * 
 * @author jerry
 * @ClassName: findKthLargest_215
 * @Description:TODO(描述这个类的作用)
 * @date 2022年12月7日 下午2:35:55
 */
public class findKthLargest_215 {

	// for test
	public static int[] generateRandomArray(int maxSize, int maxValue) {
		int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
		for (int i = 0; i < arr.length; i++) {
			// [-? , +?]
			arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
		}
		return arr;
	}

	// for test
	public static int[] copyArray(int[] arr) {
		if (arr == null) {
			return null;
		}
		int[] res = new int[arr.length];
		for (int i = 0; i < arr.length; i++) {
			res[i] = arr[i];
		}
		return res;
	}

	// for test
	public static boolean isEqual(int[] arr1, int[] arr2) {
		if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
			return false;
		}
		if (arr1 == null && arr2 == null) {
			return true;
		}
		if (arr1.length != arr2.length) {
			return false;
		}
		for (int i = 0; i < arr1.length; i++) {
			if (arr1[i] != arr2[i]) {
				return false;
			}
		}
		return true;
	}

	// for test
	public static void printArray(int[] arr) {
		if (arr == null) {
			return;
		}
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}

	// 生成随机数组测试
	public static void main(String[] args) {
		int testTime = 500000;
		int maxSize = 100;
		int maxValue = 100;
		boolean pass = true;
		System.out.println("测试开始，没有打印出错信息说明测试通过");
		for (int i = 0; i < testTime; i++) {
			int k = (int) (Math.random() * maxSize) + 1;
			int[] arr = generateRandomArray(maxSize, maxValue);

			int[] arr1 = copyArray(arr);
			int[] arr2 = copyArray(arr);

			int ans1 = new findKthLargest_215().findKthLargest(arr1, k);
			int ans2 = new findKthLargest_215().findKthLargest1(arr2, k);
			if (ans1 != ans2) {
				pass = false;
				System.out.println("出错了！");
				printArray(arr1);
				System.out.println(k);
				System.out.println(ans1);
				System.out.println(ans2);
				break;
			}
		}
		System.out.println("测试结束了，测试了" + testTime + "组，是否所有测试用例都通过？" + (pass ? "是" : "否"));
	}
//++++++++++++++++++++++++

	public int findKthLargest(int[] nums, int k) {
		k = Math.min(nums.length, k);
		if (nums == null || nums.length == 0)
			return 0;
		k--; // 第k大，k比下标大1
		int l = 0, r = nums.length - 1, index = 0;
		while (true) {
			index = l + new Random().nextInt(r - l + 1);
			int[] range = partition(nums, l, r, nums[index]);
			if (k < range[0]) {
				r = range[0] - 1;
			} else if (k > range[1]) {
				l = range[1] + 1;
			} else {
				return nums[k];
			}
		}
	}

//	public static void main(String[] args) {
//		int arr[] = new int[] { 9, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9 };
//		System.out.println(JSON.toJSONString(new findKthLargest_215().partition(arr, 0, arr.length - 1, 5)));
//	}

	// nums[] ...i...l...target...target......j... 降序
	private int[] partition(int[] nums, int i, int j, int target) {
		int sameSize = 0;
		int l = i - 1;
		while (i <= j) {
			if (nums[i] > target) {
				swap(nums, i++, ++l);
			} else if (nums[i] < target) {
				swap(nums, i, j--);
			} else {
				i++;
				sameSize++;
			}
		}
		return new int[] { l + 1, l + sameSize };
	}

	private void swap(int[] nums, int l, int r) {
		int tmp = nums[l];
		nums[l] = nums[r];
		nums[r] = tmp;
	}

	public int findKthLargest1(int[] nums, int k) {
		k = Math.min(nums.length, k);
		if (nums == null || nums.length == 0)
			return 0;
		PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				return o1 - o2;
			}
		});
		for (int i = 0; i < nums.length; i++) {
			if (queue.size() == k) {
				if (queue.peek() < nums[i]) {
					queue.poll();
					queue.offer(nums[i]);
				}
			} else {
				queue.offer(nums[i]);
			}
		}
		return queue.peek();
	}

}
